package com.leetcode.partition7;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/8/19 10:59
 */
public class LC654最大二叉树 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private TreeNode dfs(int[] nums, int l, int r) {
        if (l > r) return null;
        //找出区间最大
        int maxi = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > nums[maxi]) {
                maxi = i;
            }
        }
        TreeNode tr = new TreeNode(nums[maxi]);
        tr.left = dfs(nums, l, maxi - 1);
        tr.right = dfs(nums, maxi + 1, r);
        return tr;
    }
}
